/* 【构建成绩数组】 page 3 剑指offer from牛客网
 给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],
 其中B中的元素B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]。不能使用除法。
 解：
 B[i]的值可以看做矩阵中每行的乘积
 [1 A1 A2...An-2 An-1
  A0 1 A2...An-1 An-1
  A0 A1 1...An-2 An-1
 ...
  A0 A1...An-3 An-2 1]
 
 */
vector<int> multiply(const vector<int>& A){
    int n=A.size();
    vector<int> B(n,1);  //初始化为n个1
    vector<int> B0(n,1);
    vector<int> B1(n,1);
    for (int i=1; i<n; i++) {
        B0[i]=B0[i-1]*A[i-1];
    }//下三角
    for (int i=n-2; i>=0; i--) {
        B1[i]=B1[i+1]*A[i+1];
    }//上三角
    for (int i=0; i<n; i++) {
        B[i]=B0[i]*B1[i];
    }
    return B;
}
